package main

import (
	"fmt"
	"strconv"
)

func corpFlightBookings(bookings [][]int, n int) []int {
	result := make([]int, n)
	for i := 0; i < len(bookings); i++ {
		start := bookings[i][0] - 1
		end := bookings[i][1] - 1
		seats := bookings[i][2]

		result[start] += seats
		if end+1 < n {
			result[end+1] -= seats
		}
	}
	for i := 1; i < n; i++ {
		result[i] += result[i-1]
	}
	return result
}

var _k int

func smallestK(arr []int, k int) []int {
	_k = k
	ans := make([]int, k)

	if _k == 0 {
		return ans
	}
	qsort(arr, 0, len(arr)-1)
	for i := 0; i < k; i++ {
		ans[i] = arr[i]
	}
	return ans
}

func qsort(arr []int, l int, r int) {
	if l >= r {
		return
	}
	i, j, tmp := l, r, arr[l]
	for i < j {
		for i < j && arr[j] <= tmp {
			j--
		}
		for i < j && arr[i] >= tmp {
			i++
		}
		arr[i], arr[j] = arr[j], arr[i]
	}
	arr[l], arr[i] = arr[i], arr[l]
	qsort(arr, l, i-1)
	qsort(arr, i+1, r)
}

func swap(arr []int, l int, r int) {
	arr[r], arr[l] = arr[l], arr[r]
}

func fib(n int) int {
	if n <= 1 {
		return n
	}
	arr := make([]int, n+1)
	arr[0], arr[1] = 0, 1
	for i := 2; i <= n; i++ {
		arr[i] = arr[i-1] + arr[i-2]
		arr[i] %= 1000000007

	}
	return arr[n]
}

func search(nums []int, target int) int {
	l := 0
	r := len(nums) - 1
	for l < r {
		mid := (l + r) >> 1
		if nums[mid] >= target {
			r = mid
		} else {
			l = mid + 1
		}
	}
	if nums[l] != target {
		return -1
	}
	return l
}

func balancedStringSplit(s string) int {
	count := 0
	rCount := 0
	lCount := 0
	for _, c := range s {
		if c == 'R' {
			rCount++
		} else {
			lCount++
		}
		if (rCount != 0 && lCount != 0) && rCount == lCount {
			count++
			lCount = 0
			rCount = 0
		}
	}
	return count
}

func rand7() int {
	return 1
}

func rand10() int {
	//for {
	//	row := rand7()
	//	col := rand7()
	//	idx := (row-1)*7 + col
	//	if idx <= 40 {
	//		return 1 + idx%10
	//	}
	//}

	row := rand7()
	col := rand7()
	idx := (row-1)*7 + col
	for idx > 40 {
		row = rand7()
		col = rand7()
		idx = (row-1)*7 + col
	}
	return idx%10 + 1

}

func chalkReplacer(chalk []int, k int) int {
	n := len(chalk)
	sum := 0
	for _, v := range chalk {
		sum += v
	}
	remain := k % sum
	i := 0
	for ; i < n; i++ {
		if remain < chalk[i] {
			break
		}
		remain -= chalk[i]
	}
	return i
}

func max(a int, b int) int {
	if a > b {
		return a
	}
	return b
}

func checkValidString(s string) bool {
	low, high := 0, 0
	for _, v := range s {
		if v == '(' {
			low++
			high++
		} else if v == ')' {
			low--
			high--
		} else {
			low--
			high++
		}
		low = max(0, low)
		if low > high {
			return false
		}
	}
	return low == 0
}

func findPeakElement(nums []int) int {
	l := 0
	r := len(nums) - 1
	for l < r {
		mid := (l + r) / 2
		if nums[mid] <= nums[mid+1] {
			l = mid + 1
		} else {
			r = mid
		}
	}
	return l
}

func isValidSudoku(board [][]byte) bool {
	var row [10][10]bool
	var col [10][10]bool
	var area [10][10]bool

	for i := 0; i < 9; i++ {
		for j := 0; j < 9; j++ {
			tmp := board[i][j]
			if tmp == '.' {
				continue
			}
			var ind int = int(tmp - '0')
			areaCount := (i/3)*3 + (j / 3)
			if row[i][ind] || col[j][ind] || area[areaCount][ind] {
				return false
			}
			row[i][ind] = true
			col[j][ind] = true
			col[areaCount][ind] = true
		}
	}
	return true
}

func findNumberOfLIS(nums []int) int {
	n, maxLen, ans := len(nums), 0, 0
	dp := make([]int, n)
	cnt := make([]int, n)

	for i := 0; i < n; i++ {
		dp[i] = 1
		cnt[i] = 1

		for j := 0; j < i; j++ {
			if nums[i] > nums[j] {
				if dp[j]+1 > dp[i] {
					dp[i] = dp[j] + 1
					cnt[i] = cnt[j]
				} else if dp[j]+1 == dp[i] {
					cnt[i] += cnt[j]
				}
			}
		}
		if dp[i] > maxLen {
			maxLen = dp[i]
			ans = cnt[i]
		} else if dp[i] == maxLen {
			ans += cnt[i]
		}

	}

	return ans

}

func lengthOfLastWord(s string) int {
	index := len(s) - 1
	count := 0

	for index >= 0 {
		if s[index] == ' ' {
			index--
		} else {
			break
		}
	}

	for i := index; i >= 0; i-- {
		if s[i] != ' ' {
			count++
		} else {
			break
		}
	}

	return count
}

type Node struct {
	Val   int
	Prev  *Node
	Next  *Node
	Child *Node
}

var h *Node
var tail *Node

func flatten(root *Node) *Node {

	if root == nil {
		return nil
	}

	backtrack(nil, root)
	return h
}

func backtrack(pre *Node, current *Node) {
	if current == nil {
		return
	}
	if h == nil {
		//var tmp *Node = Node{current.Val, nil, nil, nil
		tmp := new(Node)
		tmp.Next = nil
		tmp.Prev = nil
		tmp.Child = nil
		tmp.Val = current.Val
		h, tail = tmp, tmp
	} else {
		tmp := new(Node)
		tmp.Val = current.Val
		tmp.Prev = tail
		tmp.Next = nil
		tmp.Child = nil

		tail.Next = tmp
		tail = tmp
	}

	var ppre *Node = pre

	if current.Child != nil {
		pre = current
		current = current.Child

		backtrack(pre, current)

		current = pre
		pre = ppre
	}

	pre = current
	current = current.Next
	backtrack(pre, current)
}

func numDecodings(s string) int {
	const mod int = 1e9 + 7

	a, b, c := 0, 1, 0

	for i := 0; i < len(s); i++ {
		c = b * check1digit(s[i]) % mod
		if i > 0 {
			c = (c + a*check2digits(s[i-1], s[i])) % mod
		}
		// 上上
		a = b
		// 上
		b = c
	}
	return c
}

func check1digit(ch byte) int {
	if ch == '0' {
		return 0
	}
	if ch == '*' {
		return 9
	}
	return 1
}

func check2digits(c0 byte, c1 byte) int {
	if c0 == '*' && c1 == '*' {
		return 15
	} else if c0 == '*' {
		if c1 <= '6' {
			return 2
		}
		return 1
	} else if c1 == '*' {
		if c0 == '1' {
			return 9
		} else if c0 == '2' {
			return 6
		}
		return 0
	} else {
		if c0 != '0' && ((c0-'0')*10+(c1-'0')) <= 26 {
			return 1
		}
		return 0
	}
}

func fractionToDecimal(numerator, denominator int) string {
	if numerator%denominator == 0 {
		return strconv.Itoa(numerator / denominator)
	}

	s := []byte{}
	if numerator < 0 != (denominator < 0) {
		s = append(s, '-')
	}

	// 整数部分
	numerator = abs(numerator)
	denominator = abs(denominator)
	integerPart := numerator / denominator
	s = append(s, strconv.Itoa(integerPart)...)
	s = append(s, '.')

	// 小数部分
	indexMap := map[int]int{}
	remainder := numerator % denominator
	for remainder != 0 && indexMap[remainder] == 0 {
		indexMap[remainder] = len(s)
		remainder *= 10
		s = append(s, '0'+byte(remainder/denominator))
		remainder %= denominator
	}
	if remainder > 0 { // 有循环节
		insertIndex := indexMap[remainder]
		s = append(s[:insertIndex], append([]byte{'('}, s[insertIndex:]...)...)
		s = append(s, ')')
	}

	return string(s)
}

func abs(x int) int {
	if x < 0 {
		return -x
	}
	return x
}

func divide(dividend int, divisor int) int {
	if dividend == 0 {
		return 0
	}
	if divisor == 1 {
		return dividend
	}
	const INT_MAX = (1 << 31) - 1
	const INT_MIN = -(1 << 31)

	if divisor == -1 {
		fmt.Println(INT_MIN)
		fmt.Println(INT_MAX)
		if dividend > INT_MIN {
			return -dividend
		}
		return INT_MAX
	}

	flag := 1
	if (dividend < 0 && divisor > 0) || (dividend > 0 && divisor < 0) {
		flag = -1
	}

	if dividend < 0 {
		dividend = -dividend
	}

	if divisor < 0 {
		divisor = -divisor
	}

	result := ddd(dividend, divisor)
	if flag == -1 {
		return -result
	}
	return result
}

func ddd(a int, b int) int {
	if a < b {
		return 0
	}
	bb := b
	cnt := 1
	for bb+bb < a {
		cnt = cnt + cnt
		bb = bb + bb
	}
	return cnt + ddd(a-bb, b)
}

func main() {

	result := divide(-2147483648, -1)
	fmt.Println(result)

	//a := 12
	//
	//var p1 *int = &a
	//var p2 *int
	//
	//p2 = p1
	//
	//*p2 += 1
	//fmt.Println(*p2)
	//fmt.Println(a)
	//
	//var result = lengthOfLastWord("   fly me   to   the moon  ")
	//fmt.Println(result)
}
